package binaryTree.review;

public class QuickSort2 {

    //快速排序就是前序遍历
    public  int[]  quickSort(int[] nums){
        if (nums.length==0){
            return  null;
        }
        sort(nums,0, nums.length-1);
        return nums;
    }

    public  void sort(int[] nums,int lo,int hi){
        if (lo>=hi){
            return;
        }
        int partition = partition(nums, lo, hi);
        sort(nums,lo,partition-1);
        sort(nums,partition+1,hi);
    }


    public  int partition(int[] nums,int lo,int hi){
        int boundary=nums[lo];
        int j=lo+1;
        int k=hi;
        while (j<=k){
            //此处用ｉｆ也可以
            if (nums[j]<=boundary&&j<=hi){
                j++;
            }
            if (nums[k]>boundary&&k>lo){
                k--;
            }
            if (j>k){
                break;
            }
            swap(nums,j,k);
        }
        swap(nums,lo,k);
        return  k;
    }

    public  void  swap(int[] nums,int k,int j){
        int temp=nums[j];
        nums[j]=nums[k];
        nums[k]=temp;
    }

    public static void main(String[] args) {
        QuickSort2 quickSort2 = new QuickSort2();
//        int[] nums={2,5,6,4,1};
        int[] nums=new int[]{2,5,3,2,4,1,6};
        int[] sort = quickSort2.quickSort(nums);
        for (int a:sort
             ) {
            System.out.println(a);

        }
    }





}
